package 栈;

import java.util.ArrayDeque;
import java.util.Deque;

public class No402移掉K位数字 {

    /**
     * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
     *
     * 注意:
     *
     * num 的长度小于 10002 且 ≥ k。
     * num 不会包含任何前导零。
     * 示例 1 :
     *
     * 输入: num = "1432219", k = 3
     * 输出: "1219"
     * 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
     * 示例 2 :
     *
     * 输入: num = "10200", k = 1
     * 输出: "200"
     * 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
     * 示例 3 :
     *
     * 输入: num = "10", k = 2
     * 输出: "0"
     * 解释: 从原数字移除所有的数字，剩余为空就是0。
     */

    public String removeKdigits(String num, int k) {

        if(num.length()<=k){
            return "0";
        }

        Deque<Character> stack=new ArrayDeque<>();
        char[] arr = num.toCharArray();
        stack.addLast(arr[0]);

        /**
         * 需要保证靠前的数字尽可能小。
         */
        for (int i = 1; i < arr.length; i++) {
            //相等的就不去除,例子: 112 1  相等去除的话: 12  正确:11
            while (!stack.isEmpty()&&arr[i]<stack.peekLast()&&k>0){
                stack.pollLast();
                k--;
            }
            stack.addLast(arr[i]);
        }

        /**
         * 前面尽可能小了,那么删除后面
         */
        while (k!=0){
            stack.removeLast();
            k--;
        }

        StringBuilder sb=new StringBuilder();
        while (!stack.isEmpty()&&stack.peekFirst()=='0'){
            stack.pollFirst();
        }
        while (!stack.isEmpty()){
            sb.append(stack.pollFirst());
        }
        String result = sb.toString();
        return result.length()==0?"0":result;
    }

}
